package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: 147. Insertion Sort List
 * @author: STU756
 * @create: 2020-08-17 21:17
 */
public class Pro0147 {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = head;
        ListNode pre = null;
        while(cur!=null) {
            pre = dummy;
            while(pre.next !=null && pre.next.val < cur.val){
                pre = pre.next;
            }
            ListNode preNextNode = pre.next;
            pre.next = cur;
            cur = cur.next;
            pre.next.next = preNextNode;
        }
        return dummy.next;
    }
}
